package Levenshtein;

public class Levenshtein {
	   public static int LevenshteinDistance(String source, String target)
       {
           int m = source.length();
           int n = target.length();

           // inicijalizacija matrice
           int[][] d = new int[m + 1][ n + 1];
           // prvo popuni celu matricu nulama
           for (int i = 0; i < m + 1; i++)
           {
               for (int j = 0; j < n + 1; j++)
               {
                   d[i][ j] = 0;
               }

           }

           // inicijalizacija prve kolone
           // source moze biti transformisan u prazan string izbacivanjem svih karaktera iz source
           for (int i = 1; i <= m; i++)
           {
               d[i][ 0] = i;
           }

           // inicijalizacija prvog reda
           // do targeta se moze doci od praznog stringa ubacivanjem svih karaktera iz target
           for (int j = 1; j <= n; j++)
           {
               d[0][ j] = j;
           }

           for (int j = 1; j <= n; j++)
           {
               for (int i = 1; i <= m; i++)
               {
                   if (source.charAt(i - 1) == target.charAt(j - 1))
                   {
                       d[i][j] = d[i - 1][j - 1];
                   }
                   else if ((source.charAt(i - 1) == 'c' && target.charAt(j - 1) == 'č') || (source.charAt(i - 1) == 'c' && target.charAt(j - 1) == 'ć') || (source.charAt(i - 1) == 's' && target.charAt(j - 1) == 'š')
                		   || (source.charAt(i - 1) == 'd' && target.charAt(j - 1) == 'đ') || (source.charAt(i - 1) == 'o' && target.charAt(j - 1) == 'e'))
                   {
                       d[i][ j] = d[i - 1][ j - 1];
                   }
                   else
                   {
                       d[i][ j] = Math.min(Math.min(d[i - 1][ j] + 1, // deletion
                                           d[i][ j - 1] + 1), // insertion
                                           d[i - 1][ j - 1] + 1); // substitution
                   }
               }
           }
           return d[m][ n];
       }
}
